Hard Spheres on the Move

Cluster algorithms increase efficiency for systems on a lattice by flipping large numbers of connected spins at once. In "Cluster Monte Carlo algorithms", Werner Krauth summarizes work on how such algorithms can be used in a continuum hard sphere simulation.

The basic idea is to rotate particles by &pi around a randomly chosen axis. (The key observation is that this transformation is its own inverse). A practical algorithm (the pocket algorithm) chooses a collection of particles that can be rotated without any hard spheres overlapping. It starts with a single particle and rotates it. If it overlaps with any other particles, they are added to the collection. Then the new particles are tested in the same way, and the collection is built up of all the particles that need to be rotated to prevent any overlaps.

At high densities, this algorithm will fail because the pocket cluster will contain all (or most) of the particles in the system, and simply rotate the entire configuration. Despite this limitation, there are systems where these moves are useful (see the paper for some examples).

On another subject, suppose you wanted to keep the trial box size fixed, and see how the dynamics varied with density (which would be useful if one were studying the actual MC dynamics) At higher densities, the efficiency would get quite bad. Hirosi Watanabe, et al tackle this problem in A rejection-free Monte Carlo method for the hard-disk system. They use geometry rather than random sampling to determine the allowable move area (and acceptance probability). To actually choose a point, they use a rejection method (it's not clear why this method is called "rejection-free", then. Maybe because the rejections are not essential for maintaining detailed balance, and rejected moves don't need to be included in the average.). At the step of choosing a new point, the area they choose from is greatly reduced from the original trial area.